//
// Created by xili on 2024/9/19 11:11.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    long long maxSpending(vector <vector<int>> &values) {
        priority_queue < pair < int, int >, vector < pair < int, int >>, greater<>>
        pq;
        int m = values.size(), n = values[0].size();
        for (int i = 0; i < m; i++) {
            pq.emplace(values[i].back(), i);
        }
        long long ans = 0;
        for (int d = 1; d <= m * n; d++) {
            auto [v, i] = pq.top();
            pq.pop();
            ans += (long long) v * d;
            values[i].pop_back();
            if (!values[i].empty()) {
                pq.push({values[i].back(), i});
            }
        }
        return ans;
    }
};